home *** CD-ROM | disk | FTP | other *** search
/ Almathera Ten Pack 2: CDPD 1 / Almathera Ten on Ten - Disc 2: CDPD 1.iso / pd / 351-375 / 351 / pdc / pdcsrc.lzh / PDC / Analyze.c < prev    next >
C/C++ Source or Header  |  1990-04-06  |  17KB  |  738 lines
  1.  
  2. /* PDC Compiler - A Freely Distributable C Compiler for the Amiga
  3.  *                Based upon prior work by Matthew Brandt and Jeff Lydiatt.
  4.  *
  5.  * PDC Compiler release 3.3 Copyright (C) 1989 Paul Petersen and Lionel Hummel.
  6.  * PDC Software Distribution (C) 1989 Lionel Hummel and Paul Petersen.
  7.  *
  8.  * This code is freely redistributable upon the conditions that this 
  9.  * notice remains intact and that modified versions of this file not be 
  10.  * distributed as part of the PDC Software Distribution without the express
  11.  * consent of the copyright holders.
  12.  *
  13.  *------------------------------------------------------------------
  14.  *
  15.  * $Log:    Analyze.c,v $
  16.  * Revision 3.33  90/04/04  02:25:11  lionel
  17.  * Added unsigned multiply, divide, and modulo expression handling.
  18.  * 
  19.  * Revision 3.32  90/02/03  16:22:48  lionel
  20.  * None
  21.  * 
  22.  *------------------------------------------------------------------
  23.  */
  24.  
  25. /*
  26.  * Analyze.c
  27.  * 
  28.  * This module will step through the parse tree and find all optimizable
  29.  * expressions. at present these expressions are limited to expressions that
  30.  * are valid throughout the scope of the function. the list of optimizable
  31.  * expressions is:
  32.  * 
  33.  * Constants, global and static addresses, auto addresses, contents of auto
  34.  * addresses.
  35.  * 
  36.  * Contents of auto addresses are valid only if the address is never referred to
  37.  * without dereferencing.
  38.  * 
  39.  * Scan will build a list of optimizable expressions which opt1 will replace
  40.  * during the second optimization pass.
  41.  */
  42.  
  43. #include        <stdio.h>
  44. #include        "C.h"
  45. #include        "Expr.h"
  46. #include        "Gen.h"
  47. #include        "Cglbdec.h"
  48. #include        <stab.h>
  49.  
  50. extern struct amode push[], pop[];
  51. extern struct amode *gen_expr(), *makedreg(), *makeareg(), *make_mask();
  52.  
  53. #ifdef  GENERATE_DBX
  54. extern char    *dbx_addreg();
  55.  
  56. #endif
  57. extern char    *xalloc();
  58.  
  59. static struct cse *olist;   /* list of optimizable expressions */
  60.  
  61. int
  62. equalnode(node1, node2)
  63.  
  64. /*
  65.  * equalnode will return 1 if the expressions pointed to by node1 and node2
  66.  * are equivalent.
  67.  */
  68.     register struct enode *node1, *node2;
  69. {
  70.     if (node1 == NULL || node2 == NULL)
  71.         return FALSE;
  72.  
  73.     if (node1->nodetype != node2->nodetype)
  74.         return FALSE;
  75.  
  76.     if (node1->v.i == node2->v.i) {
  77.         if (node1->nodetype == en_icon || node1->nodetype == en_labcon ||
  78.         node1->nodetype == en_nacon || node1->nodetype == en_autocon)
  79.             return TRUE;
  80.     }
  81.  
  82.     if (lvalue(node1) && equalnode(node1->v.p[0], node2->v.p[0]))
  83.         return TRUE;
  84.  
  85.     return FALSE;
  86. }
  87.  
  88. struct cse     *
  89. searchnode(node)
  90.  
  91. /*
  92.  * searchnode will search the common expression table for an entry that
  93.  * matches the node passed and return a pointer to it.
  94.  */
  95.     register struct enode *node;
  96. {
  97.     register struct cse *csp;
  98.  
  99.     for (csp = olist; csp != NULL; csp = csp->next)
  100.         if (equalnode(node, csp->exp))
  101.             return csp;
  102.  
  103.     return NULL;
  104. }
  105.  
  106. struct enode   *
  107. copynode(node)
  108.  
  109. /*
  110.  * copy the node passed into a new enode so it wont get corrupted during
  111.  * substitution.
  112.  */
  113.     struct enode   *node;
  114. {
  115.     struct enode   *temp;
  116.  
  117.     if (node == NULL)
  118.         return NULL;
  119.     temp = (struct enode *) xalloc(sizeof(struct enode));
  120.     temp->nodetype = node->nodetype;
  121.     temp->v.p[0] = node->v.p[0];
  122.     temp->v.p[1] = node->v.p[1];
  123.     return temp;
  124. }
  125.  
  126. struct cse     *
  127. enternode(node, duse)
  128.  
  129. /*
  130.  * enternode will enter a reference to an expression node into the common
  131.  * expression table. duse is a flag indicating whether or not this reference
  132.  * will be dereferenced.
  133.  */
  134.     struct enode   *node;
  135.     int             duse;
  136. {
  137.     struct cse     *csp;
  138.  
  139.     if ((csp = searchnode(node)) == NULL) { /* add to tree */
  140.         csp = (struct cse *) xalloc(sizeof(struct cse));
  141.         csp->next = olist;
  142.         csp->uses = 1;
  143.         csp->duses = (duse != 0);
  144.         csp->exp = copynode(node);
  145.         csp->voidf = FALSE;
  146.         olist = csp;
  147.         return csp;
  148.     }
  149.     ++(csp->uses);
  150.     if (duse)
  151.         ++(csp->duses);
  152.     return csp;
  153. }
  154.  
  155. struct cse     *
  156. voidauto(node)
  157.  
  158. /*
  159.  * voidauto will void an auto dereference node which points to the same auto
  160.  * constant as node.
  161.  */
  162.     struct enode   *node;
  163. {
  164.     struct cse     *csp;
  165.  
  166.     csp = olist;
  167.     while (csp != NULL) {
  168.         if (lvalue(csp->exp) && equalnode(node, csp->exp->v.p[0])) {
  169.             if (csp->voidf)
  170.                 return NULL;
  171.             csp->voidf = TRUE;
  172.             return csp;
  173.         }
  174.         csp = csp->next;
  175.     }
  176.     return NULL;
  177. }
  178.  
  179. void
  180. scanexpr(node, duse)
  181.  
  182. /*
  183.  * scanexpr will scan the expression pointed to by node for optimizable
  184.  * subexpressions. when an optimizable expression is found it is entered into
  185.  * the tree. if a reference to an autocon node is scanned the corresponding
  186.  * auto dereferenced node will be voided. duse should be set if the
  187.  * expression will be dereferenced.
  188.  */
  189.     struct enode   *node;
  190. {
  191.     struct cse     *csp, *csp1;
  192.  
  193.     if (node == NULL)
  194.         return;
  195.  
  196.     switch (node->nodetype) {
  197.     case en_icon:
  198.     case en_labcon:
  199.     case en_nacon:
  200.         enternode(node, duse);
  201.         break;
  202.     case en_autocon:
  203.         if ((csp = voidauto(node)) != NULL) {
  204.             csp1 = enternode(node, duse);
  205.             csp1->uses = (csp1->duses += csp->uses);
  206.         }
  207.         else
  208.             csp1 = enternode(node, duse);
  209.         csp1->voidf = TRUE;
  210.         break;
  211.     case en_b_ref:
  212.     case en_ub_ref:
  213.     case en_w_ref:
  214.     case en_uw_ref:
  215.     case en_l_ref:
  216.     case en_ul_ref:
  217.         if (node->v.p[0]->nodetype == en_autocon) {
  218.             csp = enternode(node, 1);
  219.             csp1 = searchnode(node->v.p[0]);
  220.             if (csp1 != NULL && csp1->voidf)
  221.                 csp1 = voidauto(node->v.p[0]);
  222.         }
  223.         else
  224.             scanexpr(node->v.p[0], 1);
  225.         break;
  226.  
  227.     case en_cbl:
  228.     case en_cbw:
  229.     case en_cwl:
  230.     case en_clf:
  231.     case en_cld:
  232.     case en_cfd:
  233.     case en_cfl:
  234.     case en_cdl:
  235.     case en_cdf:
  236.  
  237.     case en_uminus:
  238.     case en_compl:
  239.     case en_not:
  240.     case en_info:
  241.         scanexpr(node->v.p[0], duse);
  242.         break;
  243.  
  244.     case en_ainc:
  245.     case en_adec:
  246.     case en_faincs:
  247.     case en_fadecs:
  248.     case en_faincd:
  249.     case en_fadecd:
  250.         scanexpr(node->v.p[0], 0);
  251.         scanexpr(node->v.p[1], 0);
  252.         break;
  253.  
  254.     case en_asadd:
  255.     case en_assub:
  256.     case en_add:
  257.     case en_sub:
  258.     case en_mul:
  259.     case en_umul:
  260.     case en_div:
  261.     case en_udiv:
  262.     case en_lsh:
  263.     case en_rsh:
  264.     case en_mod:
  265.     case en_umod:
  266.     case en_and:
  267.     case en_or:
  268.     case en_xor:
  269.     case en_lor:
  270.     case en_land:
  271.     case en_eq:
  272.     case en_ne:
  273.     case en_gt:
  274.     case en_ugt:
  275.     case en_ge:
  276.     case en_uge:
  277.     case en_lt:
  278.     case en_ult:
  279.     case en_le:
  280.     case en_ule:
  281.     case en_asmul:
  282.     case en_asdiv:
  283.     case en_asmod:
  284.     case en_asumul:
  285.     case en_asudiv:
  286.     case en_asumod:
  287.     case en_aslsh:
  288.     case en_asrsh:
  289.     case en_asand:
  290.     case en_asor:
  291.     case en_aseor:
  292.     case en_cond:
  293.     case en_void:
  294.     case en_assign:
  295.         scanexpr(node->v.p[0], 0);
  296.         scanexpr(node->v.p[1], 0);
  297.         break;
  298.     case en_fcall:
  299.         if (node->v.p[0]->nodetype == en_nacon) {
  300.             if (strncmp(node->v.p[0]->v.sp, "__BUILTIN_", 10) == 0) {
  301.                 scanexpr(node->v.p[1], 0);
  302.                 return;
  303.             }
  304.             if (strncmp(node->v.p[0]->v.sp, "__LIBCALL_", 10) == 0) {
  305.                 scanexpr(node->v.p[1], 0);
  306.                 return;
  307.             }
  308.         }
  309.         scanexpr(node->v.p[0], 1);
  310.         scanexpr(node->v.p[1], 0);
  311.         break;
  312.  
  313.     case en_fnegs:
  314.     case en_fadds:
  315.     case en_fsubs:
  316.     case en_fmuls:
  317.     case en_fdivs:
  318.     case en_fmods:
  319.  
  320.     case en_fnegd:
  321.     case en_faddd:
  322.     case en_fsubd:
  323.     case en_fmuld:
  324.     case en_fdivd:
  325.     case en_fmodd:
  326.     case en_d_ref:
  327.     case en_f_ref:
  328.     case en_m_ref:
  329.         break;
  330.     }
  331. }
  332.  
  333. void
  334. scan(block)
  335.  
  336. /*
  337.  * scan will gather all optimizable expressions into the expression list for
  338.  * a block of statements.
  339.  */
  340.     struct snode   *block;
  341. {
  342.     while (block != NULL) {
  343.         switch (block->stype) {
  344.         case st_return:
  345.         case st_expr:
  346.             opt4(&block->exp);
  347.             scanexpr(block->exp, 0);
  348.             break;
  349.         case st_while:
  350.         case st_do:
  351.             opt4(&block->exp);
  352.             scanexpr(block->exp, 0);
  353.             scan(block->s1);
  354.             break;
  355.         case st_for:
  356.             opt4(&block->label);
  357.             scanexpr(block->label, 0);
  358.             opt4(&block->exp);
  359.             scanexpr(block->exp, 0);
  360.             scan(block->s1);
  361.             opt4(&block->s2);
  362.             scanexpr(block->s2, 0);
  363.             break;
  364.         case st_if:
  365.             opt4(&block->exp);
  366.             scanexpr(block->exp, 0);
  367.             scan(block->s1);
  368.             scan(block->s2);
  369.             break;
  370.         case st_switch:
  371.             opt4(&block->exp);
  372.             scanexpr(block->exp, 0);
  373.             scan(block->s1);
  374.             break;
  375.         case st_case:
  376.             scan(block->s1);
  377.             break;
  378.         case st_goto:
  379.         case st_label:
  380.         case st_break:
  381.         case st_continue:
  382.         case st_comment:
  383.             break;
  384.         }
  385.         block = block->next;
  386.     }
  387. }
  388.  
  389. void
  390. exchange(c1)
  391.  
  392. /*
  393.  * exchange will exchange the order of two expression entries following c1 in
  394.  * the linked list.
  395.  */
  396.     struct cse    **c1;
  397. {
  398.     struct cse     *csp1, *csp2;
  399.  
  400.     csp1 = *c1;
  401.     csp2 = csp1->next;
  402.     csp1->next = csp2->next;
  403.     csp2->next = csp1;
  404.     *c1 = csp2;
  405. }
  406.  
  407. int
  408. desire(csp)
  409.  
  410. /*
  411.  * returns the desirability of optimization for a subexpression.
  412.  */
  413.     struct cse     *csp;
  414. {
  415.     struct enode   *ep1;
  416.  
  417.     if (csp->voidf)
  418.         return 0;
  419.  
  420.     ep1 = csp->exp;
  421.  
  422.     if (ep1->nodetype == en_icon && ep1->v.i < 16 && ep1->v.i >= 0)
  423.         return (0);
  424.  
  425.     if (lvalue(csp->exp))
  426.         return 2 * csp->uses;
  427.  
  428.     return csp->uses;
  429. }
  430.  
  431. int
  432. bsort(list)
  433.  
  434. /*
  435.  * bsort implements a bubble sort on the expression list.
  436.  */
  437.     struct cse    **list;
  438. {
  439.     int             rc;
  440.     struct cse     *csp1, *csp2;
  441.  
  442.     csp1 = *list;
  443.     if (csp1 == NULL || csp1->next == NULL)
  444.         return 0;
  445.     rc = bsort(&(csp1->next));
  446.     csp2 = csp1->next;
  447.     if (desire(csp1) < desire(csp2)) {
  448.         exchange(list);
  449.         return 1;
  450.     }
  451.     return rc;
  452. }
  453.  
  454. void
  455. allocate()
  456.  
  457. /*
  458.  * allocate will allocate registers for the expressions that have a high
  459.  * enough desirability.
  460.  */
  461. {
  462.     struct cse     *csp;
  463.     struct enode   *exptr;
  464.     int             datareg, addreg, mask;
  465.     struct amode   *ap, *ap2;
  466.  
  467.     datareg = 3;
  468.     addreg = 10;
  469.     mask = 0;
  470.     while (bsort(&olist));  /* sort the expression list */
  471.     for (csp = olist; csp != NULL; csp = csp->next) {
  472.         csp->reg = -1;
  473.         if (desire(csp) >= 3) {
  474.             if (csp->duses > (csp->uses / 5)) {
  475.                 if (lvalue(csp->exp) && datareg < 8)
  476.                     csp->reg = datareg++;
  477.                 else if (addreg < 8 + Options.Frame)
  478.                     csp->reg = addreg++;
  479.                 else if (datareg < 8)
  480.                     csp->reg = datareg++;
  481.             }
  482.         }
  483.         if (csp->reg != -1)
  484.             mask = mask | (1 << csp->reg);
  485.     }
  486.  
  487.     if (mask != 0)
  488.         gen_code(op_movem, 4, make_mask(mask), push);
  489.  
  490.     save_mask = mask;
  491.  
  492.     for (csp = olist; csp != NULL; csp = csp->next) {
  493.         if (csp->reg != -1) {   /* see if preload needed */
  494.             exptr = csp->exp;
  495.             if (!lvalue(exptr) || (exptr->v.p[0]->v.i > 0)) {
  496.                 initstack();
  497.                 ap = gen_expr(exptr, F_ALL, 4);
  498.                 if (csp->reg < 8) {
  499.                     ap2 = makedreg((enum e_am) (csp->reg));
  500.                     if (ap->mode == am_immed)
  501.                         make_legal(ap, F_AREG, 4);
  502.                     gen_code(op_move, 4, ap, ap2);
  503.                 }
  504.                 else {
  505.                     ap2 = makeareg((enum e_am) (csp->reg - 8));
  506.                     gen_code(op_move, 4, ap, ap2);
  507.                 }
  508.                 freeop(ap);
  509.             }
  510.         }
  511.     }
  512. }
  513.  
  514. void
  515. repexpr(node)
  516.  
  517. /*
  518.  * repexpr will replace all allocated references within an expression with
  519.  * tempref nodes.
  520.  */
  521.     struct enode   *node;
  522. {
  523.     struct cse     *csp;
  524.  
  525.     if (node == NULL)
  526.         return;
  527.     switch (node->nodetype) {
  528.     case en_icon:
  529.     case en_nacon:
  530.     case en_labcon:
  531.     case en_autocon:
  532.         if ((csp = searchnode(node)) != NULL)
  533.             if (csp->reg > 0) {
  534.                 node->nodetype = en_tempref;
  535.                 node->v.i = csp->reg;
  536.             }
  537.         break;
  538.     case en_stabs:
  539.     case en_stabn:
  540.         if (node->v.dp != NULL && node->v.dp->ref != NULL) {
  541.             if ((csp = searchnode(node->v.dp->ref)) != NULL) {
  542.                 if (csp->reg > 0) {
  543.                     node->v.dp->tag = N_RSYM;
  544. #ifdef  GENERATE_DBX
  545.                     node->v.dp->sp = dbx_addreg(node->v.dp->sp);
  546. #endif
  547.                     node->v.dp->ref->nodetype = en_tempref;
  548.                     node->v.dp->ref->v.i = csp->reg;
  549.                 }
  550.             }
  551.         }
  552.         break;
  553.     case en_b_ref:
  554.     case en_ub_ref:
  555.     case en_w_ref:
  556.     case en_uw_ref:
  557.     case en_l_ref:
  558.     case en_ul_ref:
  559.     case en_m_ref:
  560.     case en_f_ref:
  561.     case en_d_ref:
  562.         if ((csp = searchnode(node)) != NULL) {
  563.             if (csp->reg > 0) {
  564.                 node->nodetype = en_tempref;
  565.                 node->v.i = csp->reg;
  566.             }
  567.             else
  568.                 repexpr(node->v.p[0]);
  569.         }
  570.         else
  571.             repexpr(node->v.p[0]);
  572.         break;
  573.  
  574.     case en_cbl:
  575.     case en_cbw:
  576.     case en_cwl:
  577.     case en_clf:
  578.     case en_cld:
  579.     case en_cfd:
  580.     case en_cfl:
  581.     case en_cdl:
  582.     case en_cdf:
  583.  
  584.     case en_uminus:
  585.     case en_not:
  586.     case en_compl:
  587.     case en_info:
  588.         repexpr(node->v.p[0]);
  589.         break;
  590.  
  591.     case en_ainc:
  592.     case en_adec:
  593.     case en_faincs:
  594.     case en_fadecs:
  595.     case en_faincd:
  596.     case en_fadecd:
  597.         repexpr(node->v.p[0]);
  598.         repexpr(node->v.p[1]);
  599.         break;
  600.  
  601.     case en_fnegs:
  602.     case en_fnegd:
  603.         repexpr(node->v.p[0]);
  604.         break;
  605.  
  606.     case en_add:
  607.     case en_sub:
  608.     case en_mul:
  609.     case en_umul:
  610.     case en_div:
  611.     case en_udiv:
  612.     case en_mod:
  613.     case en_umod:
  614.     case en_lsh:
  615.     case en_rsh:
  616.     case en_and:
  617.     case en_or:
  618.     case en_xor:
  619.     case en_land:
  620.     case en_lor:
  621.     case en_eq:
  622.     case en_ne:
  623.     case en_lt:
  624.     case en_ult:
  625.     case en_le:
  626.     case en_ule:
  627.     case en_gt:
  628.     case en_ugt:
  629.     case en_ge:
  630.     case en_uge:
  631.     case en_cond:
  632.     case en_void:
  633.     case en_asadd:
  634.     case en_assub:
  635.     case en_asmul:
  636.     case en_asdiv:
  637.     case en_asmod:
  638.     case en_asumul:
  639.     case en_asudiv:
  640.     case en_asumod:
  641.     case en_asor:
  642.     case en_asand:
  643.     case en_aslsh:
  644.     case en_asrsh:
  645.     case en_aseor:
  646.     case en_fcall:
  647.     case en_assign:
  648.  
  649.     case en_fadds:
  650.     case en_fsubs:
  651.     case en_fmuls:
  652.     case en_fdivs:
  653.     case en_fmods:
  654.  
  655.     case en_faddd:
  656.     case en_fsubd:
  657.     case en_fmuld:
  658.     case en_fdivd:
  659.     case en_fmodd:
  660.  
  661.         repexpr(node->v.p[0]);
  662.         repexpr(node->v.p[1]);
  663.         break;
  664.     }
  665. }
  666.  
  667. void
  668. repcse(block)
  669.  
  670. /*
  671.  * repcse will scan through a block of statements replacing the optimized
  672.  * expressions with their temporary references.
  673.  */
  674.     struct snode   *block;
  675. {
  676.     while (block != NULL) {
  677.         switch (block->stype) {
  678.         case st_stabn:
  679.         case st_stabs:
  680.             repexpr(block->exp);
  681.             break;
  682.         case st_return:
  683.         case st_expr:
  684.             repexpr(block->exp);
  685.             break;
  686.         case st_while:
  687.         case st_do:
  688.             repexpr(block->exp);
  689.             repcse(block->s1);
  690.             break;
  691.         case st_for:
  692.             repexpr(block->label);
  693.             repexpr(block->exp);
  694.             repcse(block->s1);
  695.             repexpr(block->s2);
  696.             break;
  697.         case st_if:
  698.             repexpr(block->exp);
  699.             repcse(block->s1);
  700.             repcse(block->s2);
  701.             break;
  702.         case st_switch:
  703.             repexpr(block->exp);
  704.             repcse(block->s1);
  705.             break;
  706.         case st_case:
  707.             repcse(block->s1);
  708.             break;
  709.         case st_goto:
  710.         case st_label:
  711.         case st_break:
  712.         case st_continue:
  713.         case st_comment:
  714.             break;
  715.         }
  716.         block = block->next;
  717.     }
  718. }
  719.  
  720. void
  721. opt1(block)
  722.  
  723. /*
  724.  * opt1 is the externally callable optimization routine. it will collect and
  725.  * allocate common subexpressions and substitute the tempref for all
  726.  * occurrances of the expression within the block.
  727.  * 
  728.  */
  729.     struct snode   *block;
  730. {
  731.     if (Options.Optimize) {
  732.         olist = NULL;
  733.         scan(block);    /* collect expressions */
  734.         allocate(); /* allocate registers */
  735.         repcse(block);  /* replace allocated expressions */
  736.     }
  737. }
  738.